class Solution {//leetcode23——N皇后
private:
    void dfs(int line){
        if(line==_n){
            ret.push_back(path);
            return;
        }
        for(int i=0;i<_n;i++){
            if(col[i]==false&&posi_slope[line-i+_n-1]==false&&nega_slope[line+i]==false){
                path[line][i]='Q';
                col[i]=posi_slope[line-i+_n-1]=nega_slope[line+i]=true;
                dfs(line+1);
                path[line][i]='.';
                col[i]=posi_slope[line-i+_n-1]=nega_slope[line+i]=false;
            }
        }
    }
public:
    vector<vector<string>> solveNQueens(int n) {
        _n=n;
        path.resize(n);
        for(int i=0;i<n;i++){
            path[i].append(n,'.');
        }
        col.resize(n,false);
        posi_slope.resize(2*n,false);
        nega_slope.resize(2*n,false);
        dfs(0);
        return ret;
    }
private:
    vector<vector<string>> ret;
    vector<string> path;
    vector<bool> col;
    vector<bool> posi_slope;
    vector<bool> nega_slope;
    int _n;
};